/**
 * 数列满足 SIGMA{fi ^ 2, i从1到N} = f(N) * f(N + 1)
 * 推导一下就可以发现该数列是f1乘以Fib数列，即
 * f1, f1, 2f1, 3f1, 5f1, 8f1, ...
 * 然后题目给定X和M，当存在某个k满足f(k)==X时，求X的阶乘在M进制下末尾0的数量
 * 否则求z皇后的方案总数，z = X % min(13, M) + 1
 * 首先最多只需13皇后，打表即可。
 * 其次题目已经指定f1=1，所以就是Fib数列。
 * 末尾0的数量，只需将M分解质因子，对每一个质因子均求出所含数量，取最小即可
 * 但不能简单的直接除取最大的那个因子积，否则只能通过95%
 */
#include <bits/stdc++.h>
using namespace std;

#include <bits/extc++.h>
using namespace __gnu_pbds;

using llt = long long;

const array<llt, 14> Ans = {
    0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712
};

vector<llt> F;

llt X;
int M;

void init(){
    F.reserve(91);
    F.emplace_back(0);
    F.emplace_back(1);
    for(int i=2;i<91;++i) F.emplace_back(*----F.end() + *--F.end());
    while(F.back() > 1E18) F.pop_back();
    return;
}

llt proc(){
    map<int, int> mm;
    int m = M, mx = 0, km = 0, pm = 0;
    for(int i=2;m!=1;++i){
        if(m % i == 0){
            int k = 0, tmp = 1;
            while(0 == m % i) m /= i, ++k, tmp *= i;
            mm[i] = k;
        } 
    }

    llt ans = -1;
    for(const auto & p : mm){
        llt x = X, tt = 0;
        while(x){
            tt += x / p.first;
            x /= p.first;
        } 
        tt /= p.second;
        if(-1 == ans or tt < ans) ans = tt;
    }
    return ans;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
    init();
    cin >> X >> M;
    auto it = find(F.begin(), F.end(), X);
    if(it == F.end()){
        return cout << Ans[X % min(13, M) + 1] << "\n", 0;
    }
    cout << proc() << "\n";
    return 0;
}